package pers.vic.basics.algorithm.monotone;

import com.sun.deploy.util.SyncAccess;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * @author Vic.xu
 * @description:
 * @date: 2021/1/22 0022 16:34
 */
public class M_03 {
    /*
    能看到的帽子数 单调栈
     */

    public static void main(String[] args) {
        System.out.println(123);
        int[] nums = {4, 3, 8, 5, 7, 1, 2};
        /*
         先文字描述一下：
          6：入栈   [0(6)]
          3 < 6  符合 入栈 [1(3),0（6）]
          4> 3 不符合  3 出栈  res[1] = 2-1-1
          4 入栈 [2(4），0（6）]
          5>4 bu 符合 4 出栈 res[2]  = 3-2-1
          5入栈[3(5），0（6）]
          7> 5 5出栈   res[4] = 4-3-1
          7 > 6 6 出栈 res[0] = 4 -0-1 = 3
          7 入栈
          1 入栈
          2>1 1 出栈


         */

        int[] res = new int[nums.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < nums.length; i++) {

            while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
                res[stack.peek()] = i - stack.peek() - 1;
                stack.pop();
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            res[stack.peek()] = nums.length - stack.peek() -1;
            stack.pop();
        }
        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(res));
    }
}
